package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 * <p>
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回
 * <p>
 * <p>
 * 回溯解法
 * 使用一个字符串拼接结果 每次拼接完成时 触发回溯 类似迷宫
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-07 09':19
 */
public class LetterCombinations {


    public static void main(String[] args) {
        System.out.println(letterCombinations3("234"));
        //System.out.println('a' +1);

    }

    public static List<String> letterCombinations(String digits) {
        if (digits.equalsIgnoreCase("")) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();

        char[] ch = digits.toCharArray();
        //记录每个数字对应的Y
        Stack<Integer> stack = new Stack();
        //坐标列表
        String s = "";
        //移动指针的x坐标
        stack.push(0);
        //当回溯到起点 且 起点的y大于起点本身允许的y时结束
        while (!stack.isEmpty()) {
            //未到末端 则一直往末端移动
            if (stack.size() - 1 < ch.length - 1) {
                s = s + (char) (getValue(ch[stack.size() - 1]) + stack.peek());
                stack.push(0);
            } else if (stack.size() - 1 == ch.length - 1 && stack.peek() <= getTimes(ch[stack.size() - 1]) - 1) {
                //到末端了 且末端y未超过最大值 则字符创建成功 并将y+1
                list.add(s + (char) (getValue(ch[stack.size() - 1]) + stack.peek()));
                int y = stack.pop();
                stack.push(++y);
            } else {
                //往后推一格
                while (!stack.isEmpty()
                        && stack.peek() > getTimes(ch[stack.size() - 1]) - 1) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        break;
                    }
                    //如果退到第一个字符 还是不满足条件则 程序直接退出
                    int y = stack.pop();
                    stack.push(++y);
                    s = s.substring(0, s.length() - 1);
                }
            }
        }
        return list;
    }

    public static List<String> letterCombinations2(String digits) {
        if (digits.equalsIgnoreCase("")) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();

        char[] ch = digits.toCharArray();
        //记录每个数字对应的Y
        Stack<Integer> stack = new Stack();
        //坐标列表
        StringBuilder s = new StringBuilder();
        //移动指针的x坐标
        stack.push(0);
        //当回溯到起点 且 起点的y大于起点本身允许的y时结束
        while (!stack.isEmpty()) {
            //未到末端 则一直往末端移动
            if (stack.size() - 1 < ch.length - 1) {
                s.append((char) (getValue(ch[stack.size() - 1]) + stack.peek()));
                stack.push(0);
            } else if (stack.size() - 1 == ch.length - 1 && stack.peek() <= getTimes(ch[stack.size() - 1]) - 1) {
                //到末端了 且末端y未超过最大值 则字符创建成功 并将y+1
                list.add(s.toString() + (char) (getValue(ch[stack.size() - 1]) + stack.peek()));
                int y = stack.pop();
                stack.push(++y);
            } else {
                //往后推一格
                while (!stack.isEmpty()
                        && stack.peek() > getTimes(ch[stack.size() - 1]) - 1) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        break;
                    }
                    //如果退到第一个字符 还是不满足条件则 程序直接退出
                    int y = stack.pop();
                    stack.push(++y);
                    s.deleteCharAt(s.length() - 1);
                }
            }
        }
        return list;
    }

    private static int getValue(char ch) {
        switch (ch) {
            case '2':
                return 97;
            case '3':
                return 100;
            case '4':
                return 103;
            case '5':
                return 106;
            case '6':
                return 109;
            case '7':
                return 112;
            case '8':
                return 116;
            case '9':
                return 119;
        }
        return 0;
    }

    private static Integer getTimes(char ch) {
        switch (ch) {
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '8':
                return 3;
            case '7':
            case '9':
                return 4;
        }
        return 0;
    }


    //穷举
    public static List<String> letterCombinations3(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        backtrack(combinations, digits, 0, new StringBuffer());
        return combinations;
    }

    public static void backtrack(List<String> combinations, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            int ch = getValue(digit);
            int lettersCount = getTimes(digit);
            for (int i = 0; i < lettersCount; i++) {
                combination.append((char) (ch + i));
                backtrack(combinations, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}
